home *** CD-ROM | disk | FTP | other *** search
/ BCI NET 2 / BCI NET 2.iso / archives / programming / c / objam01.lha / objam / objc / hash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-12-12  |  5.7 KB  |  232 lines
  1. /*
  2. ** ObjectiveAmiga: Hash tables for Objective C internal structures
  3. ** See GNU:lib/libobjam/ReadMe for details
  4. */
  5.  
  6.  
  7. #include <assert.h>
  8.  
  9. #include "hash.h"
  10. #include "objc.h"
  11.  
  12. #include "runtime.h"        /* for DEBUG_PRINTF */
  13.  
  14. /* These two macros determine when a hash table is full and
  15.    by how much it should be expanded respectively.
  16.  
  17.    These equations are percentages.  */
  18. #define FULLNESS(cache) \
  19.    ((((cache)->size * 75) / 100) <= (cache)->used)
  20. #define EXPANSION(cache) \
  21.   ((cache)->size * 2)
  22.  
  23. cache_ptr
  24. hash_new (unsigned int size, hash_func_type hash_func,
  25.       compare_func_type compare_func)
  26. {
  27.   cache_ptr cache;
  28.  
  29.   /* Pass me a value greater than 0 and a power of 2.  */
  30.   assert (size);
  31.   assert (!(size & (size - 1)));
  32.  
  33.   /* Allocate the cache structure.  calloc insures
  34.      its initialization for default values.  */
  35.   cache = (cache_ptr) __objc_xcalloc (1, sizeof (struct cache));
  36.   assert (cache);
  37.  
  38.   /* Allocate the array of buckets for the cache.
  39.      calloc initializes all of the pointers to NULL.  */
  40.   cache->node_table
  41.     = (node_ptr *) __objc_xcalloc (size, sizeof (node_ptr));
  42.   assert (cache->node_table);
  43.  
  44.   cache->size  = size;
  45.  
  46.   /* This should work for all processor architectures? */
  47.   cache->mask = (size - 1);
  48.     
  49.   /* Store the hashing function so that codes can be computed.  */
  50.   cache->hash_func = hash_func;
  51.  
  52.   /* Store the function that compares hash keys to
  53.      determine if they are equal.  */
  54.   cache->compare_func = compare_func;
  55.  
  56.   return cache;
  57. }
  58.  
  59.  
  60. void
  61. hash_delete (cache_ptr cache)
  62. {
  63.   node_ptr node;
  64.  
  65.  
  66.   /* Purge all key/value pairs from the table.  */
  67.   while ((node = hash_next (cache, NULL)))
  68.     hash_remove (cache, node->key);
  69.  
  70.   /* Release the array of nodes and the cache itself.  */
  71.   __objc_xfree (cache->node_table);
  72.   __objc_xfree (cache);
  73. }
  74.  
  75.  
  76. void
  77. hash_add (cache_ptr *cachep, const void *key, void *value)
  78. {
  79.   size_t indx = (*(*cachep)->hash_func)(*cachep, key);
  80.   node_ptr node = (node_ptr) __objc_xcalloc (1, sizeof (struct cache_node));
  81.  
  82.  
  83.   assert (node);
  84.  
  85.   /* Initialize the new node.  */
  86.   node->key    = key;
  87.   node->value  = value;
  88.   node->next  = (*cachep)->node_table[indx];
  89.  
  90.   /* Debugging.
  91.      Check the list for another key.  */
  92. #ifdef DEBUG
  93.   { node_ptr node1 = (*cachep)->node_table[indx];
  94.  
  95.     while (node1) {
  96.  
  97.       assert (node1->key != key);
  98.       node1 = node1->next;
  99.     }
  100.   }
  101. #endif
  102.  
  103.   /* Install the node as the first element on the list.  */
  104.   (*cachep)->node_table[indx] = node;
  105.  
  106.   /* Bump the number of entries in the cache.  */
  107.   ++(*cachep)->used;
  108.  
  109.   /* Check the hash table's fullness.   We're going
  110.      to expand if it is above the fullness level.  */
  111.   if (FULLNESS (*cachep)) {
  112.  
  113.     /* The hash table has reached its fullness level.  Time to
  114.        expand it.
  115.  
  116.        I'm using a slow method here but is built on other
  117.        primitive functions thereby increasing its
  118.        correctness.  */
  119.     node_ptr node1 = NULL;
  120.     cache_ptr new = hash_new (EXPANSION (*cachep),
  121.                   (*cachep)->hash_func,
  122.                   (*cachep)->compare_func);
  123.  
  124.     DEBUG_PRINTF ("Expanding cache %#x from %d to %d\n",
  125.           *cachep, (*cachep)->size, new->size);
  126.  
  127.     /* Copy the nodes from the first hash table to the new one.  */
  128.     while ((node1 = hash_next (*cachep, node1)))
  129.       hash_add (&new, node1->key, node1->value);
  130.  
  131.     /* Trash the old cache.  */
  132.     hash_delete (*cachep);
  133.  
  134.     /* Return a pointer to the new hash table.  */
  135.     *cachep = new;
  136.   }
  137. }
  138.  
  139.  
  140. void
  141. hash_remove (cache_ptr cache, const void *key)
  142. {
  143.   size_t indx = (*cache->hash_func)(cache, key);
  144.   node_ptr node = cache->node_table[indx];
  145.  
  146.  
  147.   /* We assume there is an entry in the table.  Error if it is not.  */
  148.   assert (node);
  149.  
  150.   /* Special case.  First element is the key/value pair to be removed.  */
  151.   if ((*cache->compare_func)(node->key, key)) {
  152.     cache->node_table[indx] = node->next;
  153.     __objc_xfree (node);
  154.   } else {
  155.  
  156.     /* Otherwise, find the hash entry.  */
  157.     node_ptr prev = node;
  158.     BOOL removed = NO;
  159.  
  160.     do {
  161.  
  162.       if ((*cache->compare_func)(node->key, key)) {
  163.         prev->next = node->next, removed = YES;
  164.         __objc_xfree (node);
  165.       } else
  166.         prev = node, node = node->next;
  167.     } while (!removed && node);
  168.     assert (removed);
  169.   }
  170.  
  171.   /* Decrement the number of entries in the hash table.  */
  172.   --cache->used;
  173. }
  174.  
  175.  
  176. node_ptr
  177. hash_next (cache_ptr cache, node_ptr node)
  178. {
  179.   /* If the scan is being started then reset the last node
  180.      visitied pointer and bucket index.  */
  181.   if (!node)
  182.     cache->last_bucket  = 0;
  183.  
  184.   /* If there is a node visited last then check for another
  185.      entry in the same bucket;  Otherwise step to the next bucket.  */
  186.   if (node) {
  187.     if (node->next)
  188.       /* There is a node which follows the last node
  189.      returned.  Step to that node and retun it.  */
  190.       return node->next;
  191.     else
  192.       ++cache->last_bucket;
  193.   }
  194.  
  195.   /* If the list isn't exhausted then search the buckets for
  196.      other nodes.  */
  197.   if (cache->last_bucket < cache->size) {
  198.     /*  Scan the remainder of the buckets looking for an entry
  199.     at the head of the list.  Return the first item found.  */
  200.     while (cache->last_bucket < cache->size)
  201.       if (cache->node_table[cache->last_bucket])
  202.         return cache->node_table[cache->last_bucket];
  203.       else
  204.         ++cache->last_bucket;
  205.  
  206.     /* No further nodes were found in the hash table.  */
  207.     return NULL;
  208.   } else
  209.     return NULL;
  210. }
  211.  
  212.  
  213. /* Given KEY, return corresponding value for it in CACHE.
  214.    Return NULL if the KEY is not recorded.  */
  215.  
  216. void *
  217. hash_value_for_key (cache_ptr cache, const void *key)
  218. {
  219.   node_ptr node = cache->node_table[(*cache->hash_func)(cache, key)];
  220.   void *retval = NULL;
  221.  
  222.   if (node)
  223.     do {
  224.       if ((*cache->compare_func)(node->key, key))
  225.         retval = node->value;
  226.       else
  227.         node = node->next;
  228.     } while (!retval && node);
  229.  
  230.   return retval;
  231. }
  232.